RAID (Redundant Array of Independent/Inexpensive Disks) is an organization of data on a plurality of disks which results in enhanced data availability and performance. As is well known, there are several levels of RAID organization with different characteristics that affect both performance of the array and availability of the data. One performance enhancing feature of RAID is "striping" which spreads user data across the disks in the array. Each disk in the RAID array is referred to as a member of the array. The user data is broken down into segments referred to as "chunks." A chunk is a group of consecutively numbered blocks that are placed consecutively on a single disk before placing blocks on a different disk. A block is the smallest unit that can be read or written to a disk. Thus, a chunk is the unit of data interleaving for a RAID array. For example, in a four disk RAID array the first chunk is placed on the first disk, the second chunk is placed on the second disk, the third chunk is placed on the third disk, the fourth chunk is placed on the fourth disk, the fifth chunk is placed on the first disk and so on.
RAID enhances data availability through data redundancy. In RAID level 4 (RAID-4) and RAID level 5 (RAID-5) data redundancy is achieved by "parity." Parity involves the use of error correction codes (ECC) such as Exclusive-OR or Reed-Solomon. Parity data is stored in the RAID array and is used to reconstruct the data if a disk fails or a data block otherwise becomes unavailable.
RAID-4 and RAID-5 are organizations of an array of n+1 disks that provide enhanced performance through the use of striping and enhanced data availability through the association of a parity block with every n data blocks. The data and parity information is distributed over the n+1 disks so that if a single disk fails or a data block on another disk is unreadable, all of the data can be recovered. RAID-4 is a level of organization for a RAID array where data blocks are arranged into chunks which are interleaved among the disks and protected by parity and all of the parity is written on a single disk. RAID-5 is a level of organization of data for a RAID array where data blocks are arranged into chunks which are interleaved among the disks and protected by parity and the parity is distributed over all of the disks in the array. In both RAID-4 and RAID-5 the ensemble or array of n+1 disks appears to the user as a single, more highly available virtual disk.
The contents of each bit of the parity block is the Exclusive-OR of the corresponding bit in each of the n corresponding data blocks. In the event of the failure of a single disk in the array, the data from a given data block on the failed disk is recovered by computing the Exclusive-OR of the contents of the corresponding parity blocks and the n-1 data blocks on the surviving disks that contributed to the parity block. The same procedure is followed if a single block or group of blocks is unavailable. A block or set of blocks is repaired by writing the regenerated data. The regeneration and repair of data for a data block or set of data blocks and the associated parity block on a disk in a RAID array is referred to as reconstruction.
RAID storage systems can be implemented in hardware or software. In the hardware implementation the RAID algorithms are built into a controller that connects to the computer I/O bus. In the software implementation the RAID algorithms are incorporated into software that runs on the main processor in conjunction with the operating system. Both the hardware and software implementations of RAID are well known to those of ordinary skill in the field.
A single application I/O request is typically for a continuous range of blocks on the "virtual" disk presented by the array. Thus, a single application I/O request can span multiple strips. A strip is a single parity chunk and all of the data chunks that contribute to it. As is well known to those of ordinary skill in the field, RAID implementations typically divide an application I/O request into a plurality of I/O requests, each of the divided I/O requests is contained within the boundaries of a single strip and each of these divided I/O requests is processed as a unit.
In the context of a single strip, a single I/O request can target a complicated geometry or pattern of data blocks. A high performance implementation of a RAID-4 or RAID-5 array uses a number of different algorithms to read and write data from the array. These operations include simple read, read modify write, reconstruct write, regenerate read repair, and non-redundant write. Each of these operations is well known to one of ordinary skill in the field. The specific algorithm to use for a particular geometric pattern of data blocks depends upon a variety of factors including whether the operation is a write or read, the number of chunks involved and whether the array is complete or is missing a disk. Thus, dealing with the complexities of error recovery and the efficient implementation of a multiplicity of read and write algorithms, each tuned for a different set of scenarios is complicated by the many patterns that a single read or a single write operation can target. Accordingly, it is desirable to reduce the complexity of the geometry of the data blocks on a strip responsive to an I/O request.